template<class T, bool Directed = true, bool Longest = false>
struct Spfa {
	static constexpr T inf = std::numeric_limits<T>::max() / 2;

	int n;
	std::vector<std::vector<std::pair<int, T>>> g;
	std::vector<T> dis;

	Spfa() {};

	Spfa(int n) : n(n), g(n) {}

	void add_Edge(int u, int v, T w) {
		if(Directed) {
			g[u].emplace_back({v, w});
		} else {
			g[u].emplace_back({v, w});
			g[v].emplace_back({u, w});
		}
	}

	bool work(int root = 0) {
		std::vector<bool> vis(n, false);
		std::vector<int> cnt(n, 0);
		if(Longest) {
			dis.assign(n, -inf);
		} else {
			dis.assign(n, inf);
		}
		dis[root] = 0;
		std::queue<int> q;
		q.push(root);
		vis[root] = true;
		while(q.size()) {
			auto u = q.front();
			q.pop();
			vis[u] = false;
			for(auto [v, w] : g[u]) {
				if(Longest) {
					if(dis[u] + w > dis[v]) {
						dis[v] = dis[u] + w;
						if((cnt[v] = cnt[u] + 1) >= n) {
							return false;
						}
						if(!vis[v]) {
							q.push(v);
							vis[v] = true;
						}
					}
				} else {
					if(dis[u] + w < dis[v]) {
						dis[v] = dis[u] + w;
						if((cnt[v] = cnt[u] + 1) >= n) {
							return false;
						}
						if(!vis[v]) {
							q.push(v);
							vis[v] = true;
						}
					}
				}
			}
		}
		return true;
	}

};